import collections
import math
class TreeAncestor(object):

    def __init__(self, n, parent):
        """
        :type n: int
        :type parent: List[int]
        """
        self.n = n
        d = collections.defaultdict(set)
        for index, num in enumerate(parent):
            d[num].add(index)
        self.p_tree = collections.defaultdict(dict)
        st = [0]
        while st:
            next_st = []
            for node in st:
                if parent[node] != -1:
                    dist = 1
                    p_node = parent[node]
                    self.p_tree[node][dist] = p_node
                    while dist in self.p_tree[p_node]:
                        self.p_tree[node][2 * dist] = self.p_tree[p_node][dist]
                        p_node = self.p_tree[p_node][dist]
                        dist *= 2
                for next_node in d[node]:
                    next_st.append(next_node)
            st = next_st





    def getKthAncestor(self, node, k):
        """
        :type node: int
        :type k: int
        :rtype: int
        """
        if not self.p_tree[node]:
            return -1
        last_dist = int(math.log2(k))
        p = 2 ** last_dist
        if p in self.p_tree[node]:
            node = self.p_tree[node][p]
            k -= p
            if k == 0:
                return node
            else:
                return self.getKthAncestor(node, k)
        else:
            return -1

